import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Test {
    // 25.【一维】一维前缀和（easy）
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        // 防止数组访问溢出
        int[] arr = new int[n + 1];
        long[] dp = new long[n + 1];
        // 读数据
        for (int i = 1; i <= n; i++) {
            arr[i] = in.nextInt();
        }
        // 处理前缀和数据
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + arr[i];
        }
        // 使用前缀和数组
        while (q > 0) {
            int l = in.nextInt();
            int r = in.nextInt();
            System.out.println(dp[r] - dp[l - 1]);
            q--;
        }
    }

    // 24. 0~n-1 中缺失的数字（easy）
    // 方法一：使用哈希表
    public static int takeAttendanceHashSet(int[] records) {
        Set<Integer> set = new HashSet<>();
        for (int record : records) {
            set.add(record);
        }
        for (int i = 0; i <= records.length; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }
        return -1;
    }

    // 方法二：直接遍历找结果
    public static int takeAttendanceTraverse(int[] records) {
        for (int i = 0; i < records.length; i++) {
            if (i != records[i]) {
                return i;
            }
        }
        return records.length;
    }

    // 方法三：位运算方法

    /**
     * 异或运算的性质：
     * 异或运算（^）具有两个关键性质：
     * 任何数和它自身异或的结果是 0，即 a ^ a = 0。
     * 任何数和 0 异或的结果是它自身，即 a ^ 0 = a 。
     * <p>
     * 遍历数组进行异或：
     * 在 for 循环中，result ^= i ^ nums[i] 这一步，是把数组下标 i 和对应位置的数组元素 nums[i] 进行异或，
     * 并累加到 result 上。
     * 例如，当 i = 0 时，result 初始为 0，就计算 0 ^ nums[0]；
     * 当 i = 1 时，计算 (之前的result) ^ 1 ^ nums[1]，依此类推。
     * 由于数组中有 n - 1 个元素，这个循环做完后，数组中存在的 n - 1 个下标和对应元素都两两配对进行了异或。
     * 那些下标和对应元素相同的数对，经过异或后结果为 0，被抵消掉了。
     * <p>
     * 与数组长度异或：
     * 最后一步 result ^= nums.length 是关键。因为前面的循环已经把现有的 n - 1 个下标和对应元素异或处理了，
     * 只剩下缺失的那个数字对应的下标没有被抵消，此时再把数组长度 n
     * （也就是最后一个未参与前面异或运算的下标）与 result 异或，根据异或性质，就能得到缺失的那个数字。
     * <p>
     * 举个简单例子，假设数组是 [0, 1, 3]，数组长度 n = 4：
     * 第一轮循环：i = 0，result = 0 ^ 0 ^ 0 = 0；
     * 第二轮循环：i = 1，result = 0 ^ 1 ^ 1 = 0；
     * 第三轮循环：i = 2，result = 0 ^ 2 ^ 3 = 1；
     * 最后与数组长度异或：result = 1 ^ 4 = 2，这个 2 就是缺失的数字。
     * <p>
     * 所以，利用异或运算的特性，巧妙地把所有现有元素与下标配对异或，
     * 最后再结合数组长度异或，就能精准找出缺失的数字。
     */
    public static int takeAttendanceXor(int[] records) {
        int ret = 0;
        for (int i = 0; i < records.length; i++) {
            ret ^= i ^ records[i];
        }
        ret ^= records.length;
        return ret;
    }

    // 方法四：数学方法（高斯求和公式）
    public static int takeAttendanceGauss(int[] records) {
        int sum = (records.length * (records.length + 1)) / 2; // 等差数列求和公式
        for (int record : records) {
            sum = sum - record;
        }
        return sum;
    }


    // 方法五：二分算法
    public static int takeAttendanceBinarySearch(int[] records) {
        int left = 0, right = records.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid) {
                left = mid + 1;
            } else {
                // record[mid] != mid
                right = mid;
            }
        }
        return records[left] == left ? left + 1 : left;
    }

    public static void main6(String[] args) {
        int[] nums = {0, 1, 2, 3, 4, 5, 6, 8};

        System.out.println("哈希表方法: " + takeAttendanceHashSet(nums)); // 7
        System.out.println("直接遍历方法: " + takeAttendanceTraverse(nums)); // 7
        System.out.println("位运算方法: " + takeAttendanceXor(nums)); // 7
        System.out.println("高斯求和公式方法: " + takeAttendanceGauss(nums)); // 7
        System.out.println("二分算法方法: " + takeAttendanceBinarySearch(nums)); // 7
    }


    // 23. 搜索旋转排序数组中的最小值（medium）
    public static int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        int x = nums[right]; // 标志一下最后的位置
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > x) {
                left = mid + 1;
            } else {
                // nums[mid] <= x
                right = mid;
            }
        }
        return nums[left];
    }

    public static void main5(String[] args) {
        // 示例1
        int[] numsForMin1 = {3, 4, 5, 1, 2};
        int min1 = findMin(numsForMin1);
        System.out.println("数组中的最小值是: " + min1); // 1

        // 示例2
        int[] numsForMin2 = {4, 5, 6, 7, 0, 1, 2};
        int min2 = findMin(numsForMin2);
        System.out.println("数组中的最小值是: " + min2); // 0

        // 示例3
        int[] numsForMin3 = {11, 13, 15, 17};
        int min3 = findMin(numsForMin3);
        System.out.println("数组中的最小值是: " + min3); // 11
    }

    // 22. 寻找峰值（medium）
    public static int findPeakElement1(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                // nums[mid] >= nums[mid + 1]
                right = mid;
            }
        }
        return left;
    }

    public static int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public static void main4(String[] args) {
        // 示例1
        int[] nums1 = {1, 2, 3, 1};
        int result1 = findPeakElement(nums1);
        System.out.println("示例1输出: " + result1); // 2

        // 示例2
        int[] nums2 = {1, 2, 1, 3, 5, 6, 4};
        int result2 = findPeakElement(nums2);
        System.out.println("示例2输出: " + result2); // 5
    }


    // 21. 山峰数组的峰顶（easy）
    public static int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] > arr[mid - 1]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    public static void main3(String[] args) {
        // 示例1
        int[] arr1 = {0, 1, 0};
        int result1 = peakIndexInMountainArray(arr1);
        System.out.println("示例1输出: " + result1); // 1

        // 示例2
        int[] arr2 = {0, 2, 1, 0};
        int result2 = peakIndexInMountainArray(arr2);
        System.out.println("示例2输出: " + result2); // 2

        // 示例3
        int[] arr3 = {24, 69, 100, 99, 79, 78, 67, 36, 26, 19};
        int result3 = peakIndexInMountainArray(arr3);
        System.out.println("示例3输出: " + result3); // 2
    }


    // 20. x 的平方根（easy）
    public static int mySqrt(int x) {
        if (x < 1) {
            return 0;
        }
        long left = 1, right = x;
        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return (int) left;
    }

    public static void main2(String[] args) {
        // 示例1
        int x1 = 4;
        int result1 = mySqrt(x1);
        System.out.println("示例1输出: " + result1); // 2

        // 示例2
        int x2 = 8;
        int result2 = mySqrt(x2);
        System.out.println("示例2输出: " + result2); // 2
    }


    // 19. 搜索插⼊位置（easy）
    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 特殊情况
        if (nums[left] < target) {
            return left + 1;
        }
        return left;
    }

    public static void main1(String[] args) {
        // 示例1
        int[] nums1 = {1, 3, 5, 6};
        int target1 = 5;
        int result1 = searchInsert(nums1, target1);
        System.out.println("示例1输出: " + result1);

        // 示例2
        int[] nums2 = {1, 3, 5, 6};
        int target2 = 2;
        int result2 = searchInsert(nums2, target2);
        System.out.println("示例2输出: " + result2);

        // 示例3
        int[] nums3 = {1, 3, 5, 6};
        int target3 = 7;
        int result3 = searchInsert(nums3, target3);
        System.out.println("示例3输出: " + result3);
    }
}
